package com.ln.prac.base.m202206.d07;

import java.util.Arrays;

/**
 * <pre>
 *  跳表
 * </pre>
 *
 * @Author zhangj
 * @Date 2022/6/8 03:01
 */
public class SkipList {

    /**
     * 最大层数
     */
    public final static int MAX_LEVEL = 32;

    /**
     * 随机层数概率，在一层以上不包括第一层的概率，层数不超过maxLevel，层数起始为1
     */
    public static double DEFAULT_P_FACTOR = 0.25;

    /**
     * 头节点
     */
    Node head = new Node(null, MAX_LEVEL);

    /**
     * 当前节点的实际层级，默认为1
     */
    int currentLevel = 1;

    public SkipList() {
    }

    /**
     * 查找值
     */
    public boolean search(int target) {
        Node searchNode = head;
        for (int i = currentLevel - 1; i >= 0; i--) {
            searchNode = findCloset(searchNode, i, target);
            if(searchNode.next[i] != null && searchNode.next[i].value == target) {
                return true;
            }
        }
        return false;
    }

    /**
     * 找到level层 value 大于node 的节点
     */
    private Node findCloset(Node node, int level, int val) {
        while ((node.next[level]) != null && val > node.next[level].value) {
            node = node.next[level];
        }
        return node;
    }

    /**
     * 节点类
     */
    static class Node {
        /**
         * 节点值
         */
        Integer value;
        /**
         * 后续节点列表
         */
        Node[] next;

        public Node(Integer value, int size) {
            this.value = value;
            this.next = new Node[size];
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", next=" + Arrays.toString(next) +
                    '}';
        }
    }

}
